# 给定一个无序的整数数组，找到其中最长上升子序列的长度。

# 输入: [10,9,2,5,3,7,101,18]
# 输出: 4
# 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

# https://leetcode-cn.com/problems/longest-increasing-subsequence/


# 第一次跪了 [10,9,2,5,3,4]
# 期待值3
# 实际输出 2
class Solution:
    def lengthOfLIS(self, nums):
        max_len = 0
        sort_list = []
        for times in range(len(nums)):
            del sort_list
            check = nums[times]
            sort_list = [check]
            for i in nums[times:] :
                if i > check:
                    check = i
                    sort_list.append(i)
            else:
                if(max_len < len(sort_list)):
                    max_len = len(sort_list)

        return max_len

    # 偷看答案 动态规划
    # 运行结果 [1, 1, 1, 2, 2, 3]
    # 我还是没看懂为什么 dp的最大值就是答案...
    # 早上有点懵 以后再看看 动画演示好像懂了?
    # https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
    def lengthOfLIS_2(self, nums):
        if not nums:
            return 0
        dp = []
        for i in range(len(nums)):
            dp.append(1)
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)



test = Solution()
re = test.lengthOfLIS_2([10,9,2,5,3,4])
print(re)
